# 多数元素： https://leetcode-cn.com/problems/majority-element/

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
            最简单的就是使用 字典计数，空间复杂度较高
        """
        n = len(nums)
        countMap = {}
        for num in nums:
            countMap[num] = countMap.get(num, 0) + 1
        
        # rst = []
        for num in countMap:
            if countMap.get(num) > n // 2:
                return num


# 还可以优化成那个一个for 写法
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
            最简单的就是使用 字典计数，空间复杂度较高
        """
        n = len(nums)
        countMap = {}
        for num in nums:
            countMap[num] = countMap.get(num, 0) + 1
            if countMap.get(num) > n // 2:
                return num 
        

# 进阶写法， O(1) 空间复杂度
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
            Boyer-Moor投票算法：看解析
        """
        n = len(nums)
        candidate = nums[0]
        count = 1
        for i in range(1, n):
            if count > 0:
                if candidate == nums[i]:
                    count += 1
                else:
                    count -= 1
            else:
                candidate = nums[i]
                count = 1
        
        return candidate


# 官网的写法，太简洁了
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate
